package leetcode.code0721;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeSet;

public class Solution1 extends Solution721 {

	class Account {
		String name;
		TreeSet<String> treeSet;
//		Set<String> emails;

		public Account(String name) {
			this.name = name;
			this.treeSet = new TreeSet<>((o1, o2) -> o1.compareTo(o2));
//			this.emails = new HashSet<>();
		}

//		public void add(String email) {
//			emails.add(email);
//			this.treeSet.add(email);
//		}

//		public TreeSet<String> getSet() {
//			return this.treeSet;
//		}

//		public void addAll(TreeSet<String> treeSet) {
//			this.treeSet.addAll(treeSet);
//		}

		public void addAll(List<String> treeSet) {
			this.treeSet.addAll(treeSet);
		}

		public List<String> getList() {
			List<String> ans = new ArrayList<>();
			ans.add(name);
			ans.addAll(this.treeSet);
			return ans;
		}

	}

	private Account[] create;// create[索引] = 账户
	private int[] leader;// leader[索引] = 代表
	private int[] size;
	private int[] stack;
	private int len;

//	1,2 （大）-lead = 9
//	2,3 （小）-lead = 1
//	3,4  	  -lead = 1
//	3,9 （超大）

	@Override
	public List<List<String>> accountsMerge(List<List<String>> accounts) {
		len = accounts.size();
		this.create = new Account[len];// 索引 - 账户
		this.leader = new int[len];// 索引 - 索引的代表索引
		this.size = new int[len]; // 索引 - 元素数量，
		this.stack = new int[len];
		int createIndex = 0;
		Map<String, Integer> accountByEmail = new HashMap<>();
		for (List<String> account : accounts) {
			Account newAccount = new Account(account.get(0));// name
			this.create[createIndex] = newAccount;
			this.leader[createIndex] = createIndex;
			this.size[createIndex] = account.size();
			int lead = createIndex;
			for (int i = 1; i < account.size(); i++) {
				String email = account.get(i);
				int exists = accountByEmail.getOrDefault(email, -1);
				if (exists != -1) {
					lead = this.merge(exists, lead);
				}
				accountByEmail.put(email, lead);
			}
			createIndex++;
		}
		List<List<String>> ans = this.mergeAccountArray(accounts);
		return ans;
	}

	private List<List<String>> mergeAccountArray(List<List<String>> accounts) {
		List<List<String>> ans = new ArrayList<>();
		for (int i = 0; i < len; i++) {
			Account account = this.create[i];
			int leaderIndex = this.findLeader(i);
			if (leaderIndex != i) {
				Account leaderAccount = this.create[leaderIndex];
				List<String> list = accounts.get(i);
				list.remove(0);
				leaderAccount.addAll(list);
				this.create[i] = null;
			}else {
				List<String> list = accounts.get(i);
				list.remove(0);
				account.addAll(list);
			}
		}
		for (Account account : this.create) {
			if (account == null)
				continue;
			ans.add(account.getList());
		}
		return ans;
	}

	private int merge(int idx1, int idx2) {
		int p1 = this.findLeader(idx1);
		int p2 = this.findLeader(idx2);
		if (p1 != p2) {
			if (this.size[p1] > this.size[p2]) {
				this.leader[p2] = p1;
				this.size[p1] += this.size[p2];
//				this.size[p2] = 0;//
				return p1;
			} else {
				this.leader[p1] = p2;
				this.size[p2] += this.size[p1];
//				this.size[p1] = 0;
				return p2;
			}
		}
		return p1;
	}

	private int findLeader(int id) {// 找到id的代表节点
		int stackp = 0;
		while (id != this.leader[id]) {
			this.stack[stackp++] = id;
			id = this.leader[id];
		}
		while (stackp > 0) {
			this.leader[this.stack[--stackp]] = id;
		}
		return id;
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug1();
	}

}
